In telecommunication networks, it is often desirable to change the link weights to engender path changes in a certain desired fashion. For example, a bank data transfer in the commercial world between a given pair of offices might need to be occasionally processed at a third intermediate office before arriving at the destination node, in which case one might alter weights of a certain subset of links to cause the route to traverse the intermediate node. In another instance, a high capacity link might suddenly become available over which the traffic between the given source-destination pair of an important customer might need to be rerouted to alleviate congestion on the current route, and maintain the desired quality of service as warranted, perhaps, by a service-level agreement.
The problem of changing routes within a network by altering the weights has been discussed in the following articles: “Traffic engineering with traditional IP routing protocols,” by B. Fortz et al., IEEE Communications Magazine, 40(10), pp 118-124, 2002; “Internet Routing and Related Topology Issues,” by W. Ben-Ameur et al., SIAM Journal of Discrete Mathematics, 17(1), pp 18-49, 2003; and “On the Inverse Shortest Path Problem,” by Pal Nilsson, 17th Nordic Teletraffic Seminar (NTS 17), Fornebu, Norway, August 2004. Very often, the techniques involve integer programming formulations because of the requirement of integrality of link weights, leading frequently to approximations such as linear relaxation.
In an abstract entitled “The Sliding Shortest Path Problem,” published on Mar. 22, 2007 in conjunction with the 20Th Cumberland Conference, May 17-19, 2007, Emory University, Atlanta, Ga., the inventor disclosed the following. Given an undirected weighted graph and a pair of vertices s and t, connected by the shortest path, and a third vertex p not lying on the shortest path, what is the minimal change in the graph weights needed to cause the shortest path between s and t to pass through vertex p? This is the type of problem often faced by network administrators in the telecommunication world. The inventor provided an algorithm for solving this problem; the approach taken is one of replacement of the weights of a set of edges of minimal cardinality with weights of “infinity.” The algorithm determines the minimum cardinality set in polynomial time. Furthermore, it is shown that it is easily extensible to pass over a given edge, instead of the given vertex, a scenario that can also occur in telecommunication networks. The algorithm disclosed minimizes the number of edges to be modified, but does not minimize the change to the weights of such edges, because changing such weights to “infinity” effectively cuts those edges out of the network. A solution to the problem is needed that does not cut such edges out of the network, because such edges are useful for carry communication traffic not related to the communication traffic to be transmitted via the newly formed shortest path. Therefore an improvement to the method presented in March 2007 is needed. The present invention is such an improvement.
There is a need for a device for and method of identifying the minimal changes that need to be made to a network for a specific demand (a single source-destination pair) to be rerouted through a desired link or vertex not already on the shortest path of the given demand, where the number of links on which weight changes are made is minimized in order to reduce the implementation time of link weight changes within the current network environment, and where the weight changes (decrements and increments) are minimized in order to cause the least amount of impact on the number of other shortest paths (routes of other demands). The present invention is such a device and method.
U.S. Pat. No. 6,321,271, entitled “CONSTRAINED SHORTEST PATH ROUTING METHOD,” discloses a two-phase method of determining the shortest weight and finding the cumulative delay from the destination to the source. U.S. Pat. No. 6,321,271 is hereby incorporated by reference into the specification of the present invention.
U.S. Pat. No. 6,765,880, entitled “METHOD AND APPARATUS FOR ELIMINATING UNPROTECTED PATHS FROM CONSIDERATION DURING COMPUTATION OF PROTECTABLE SHORTEST PATH TREE,” discloses a device for and method of finding a shortest path using the concept of a protectable link, where a protectable link is one that is a member of a loop. U.S. Pat. No. 6,765,880 is hereby incorporated by reference into the specification of the present invention.
U.S. Pat. No. 6,928,484, entitled “METHOD AND APPARATUS FOR DISCOVERING EDGE-DISJOINT SHORTEST PATH PAIRS DURING SHORTEST PATH TREE COMPUTATION,” discloses a device for and method of finding the shortest path that has an alternate path, where such a path is not necessarily the absolute shortest path. U.S. Pat. No. 6,928,484 is hereby incorporated by reference into the specification of the present invention.
U.S. Pat. No. 6,992,988, entitled “SYSTEM AND METHOD FOR DEADLOCK-FREE ROUTING ON ARBITRARY NETWORK TOPOLOGIES,” discloses a device for and method of calculating a deadlock-free set of paths by generating an ordered set of deadlock-free sub-topologies. U.S. Pat. No. 6,992,988 is hereby incorporated by reference into the specification of the present invention.
U.S. Pat. No. 7,280,481, entitled “METHOD AND APPARATUS FOR ELIMINATING UNPROTECTED PATHS FROM CONSIDERATION DURING COMPUTATION OF PROTECTABLE SHORTEST PATH TREE,” discloses a device for and method of selecting a meet node, calculating a shortest path from a source node to the meet node, calculating a shortest path from a destination node to the meet node, and concatenating the two paths to form a path from the source node to the destination node. U.S. Pat. No. 7,280,481 is hereby incorporated by reference into the specification of the present invention.
U.S. Pat. No. 7,457,286, entitled “ACCELERATING THE SHORTEST PATH PROBLEM,” discloses a method of accelerating the determination of the shortest path by grouping nodes. U.S. Pat. No. 7,457,286 is hereby incorporated by reference into the specification of the present invention.
U.S. Pat. No. 7,593,341, entitled “METHOD AND APPARATUS FOR UPDATING A SHORTEST PATH GRAPH,” discloses a device for and method of placing a subset of nodes affected by a change in weight of an arc into a heap and then determining the shortest path from the nodes placed in the heap. U.S. Pat. No. 7,593,341 is hereby incorporated by reference into the specification of the present invention.
U.S. Pat. Appl. No. 20040032831, entitled “SIMPLEST SHORTEST PATH FIRST FOR PROVISIONING OPTICAL CIRCUITS IN DENSE MESH NETWORK CONFIGURATIONS,” discloses a method of determining the shortest path using a multi-layered network path determination method and a cache strategy to cache approximate paths, rather than exact paths, and to age out cache entries just before they become incorrect, and a method of turning an approximate path into an exact path. U.S. Pat. Appl. No. 20040032831 is hereby incorporated by reference into the specification of the present invention.